package leetcode.doublepoint;

import java.util.HashMap;
import java.util.Map;

/**
 * 
 * @author 26233
 *
 *给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

 

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：

输入：s = "a", t = "a"
输出："a"
 

提示：

1 <= s.length, t.length <= 105
s 和 t 由英文字母组成
 

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-window-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode76_MinWindow {
	
	public static String minWindow(String s, String t) {
		if(t.length() > s.length()) return "";
		Map<Character, Integer> tCharCountMap = new HashMap<>();
		for(int i = 0; i < t.length(); i++) {
			Integer v = tCharCountMap.get((char)t.charAt(i)) == null ? 1 : tCharCountMap.get((char)t.charAt(i)) + 1;
			tCharCountMap.put((char)t.charAt(i), v);
		}
		int[][] sCharPosition = new int[s.length()][2];// 记录位置
		int index = 0;
		for(int i = 0; i < s.length(); i++) {
			if(tCharCountMap.containsKey(s.charAt(i))) {
				sCharPosition[index][0] = s.charAt(i);
				sCharPosition[index++][1] = i;
			}
		}
		
		int count = 0;
		int[] currentWindowCharCount = new int[128];
		int l = 0, min = 0, max = 0, minLength = s.length();
		boolean flag = false;
		for(int r = 0; r < sCharPosition.length && sCharPosition[r][0] != 0; r++) {
			currentWindowCharCount[sCharPosition[r][0]]++;
			if(currentWindowCharCount[sCharPosition[r][0]] <= tCharCountMap.get((char)sCharPosition[r][0])) {
				count++;
			}
			
			while(count == t.length()) {// 当前窗口中已存在t中的所有字符
				flag = true;
				if(sCharPosition[r][1] - sCharPosition[l][1] < minLength) {
					max = r;
					min = l;
					minLength = sCharPosition[r][1] - sCharPosition[l][1];
				}
				char removeChar = (char)sCharPosition[l][0];
				if(currentWindowCharCount[removeChar] <= tCharCountMap.get(removeChar)) {
					count--;
				}
				currentWindowCharCount[removeChar]--;
				l++;
			}
		}
		
		return flag ? s.substring(sCharPosition[min][1], sCharPosition[max][1] + 1) : "";
    }
	// 记录t中的字符需要的个数，只记录t的每个字符在s中的位置
	// 如何修改窗口的范围？先移动右指针，直到满足条件为止。然后移动左指针，直到不能满足条件为止，再移动右指针直到满足条件为止，如此循环
	// 对于存在冗余字符的情况，就需要记录每个t中的字符在窗口中的数量
	public static String minWindow2(String s, String t) {
		if(t.length() > s.length()) return "";
		int[] tCharCountArr = new int[128];
		for(int i = 0; i < t.length(); i++) {
			tCharCountArr[t.charAt(i)]++;
		}
		
		
		int[][] sCharPosition = new int[s.length()][2];// 记录位置
		int index = 0;
		for(int i = 0; i < s.length(); i++) {
			if(tCharCountArr[s.charAt(i)] > 0) {
				sCharPosition[index][0] = s.charAt(i);
				sCharPosition[index++][1] = i;
			}
		}
		
		int count = 0;
		int[] currentWindowCharCount = new int[128];
		int l = 0, min = 0, max = 0, minLength = s.length();
		boolean flag = false;
		for(int r = 0; r < sCharPosition.length && sCharPosition[r][0] != 0; r++) {
			// 出现的字符都要记录，为的是冗余字符的判断
			currentWindowCharCount[sCharPosition[r][0]]++;
			// 某个字符满足条件之后就不在增加count了
			if(currentWindowCharCount[sCharPosition[r][0]] <= tCharCountArr[sCharPosition[r][0]]) {
				count++;
			}
			
			while(count == t.length()) {// 当前窗口中已存在t中的所有字符
				flag = true;
				// 记录最小窗口的起止位置
				if(sCharPosition[r][1] - sCharPosition[l][1] < minLength) {
					max = r;// 结束位置
					min = l;// 开始位置
					minLength = sCharPosition[r][1] - sCharPosition[l][1];
				}
				char removeChar = (char)sCharPosition[l][0];
				if(currentWindowCharCount[removeChar] <= tCharCountArr[removeChar]) {// 判断窗口中是否存在多余的字符，如果存在多余的字符，那么下一个位置任然满足条件，l指针可以继续移动，
					// 否则不能满足所有字符存在的条件
					count--;
				}
				currentWindowCharCount[removeChar]--;
				l++;
			}
		}
		
		return flag ? s.substring(sCharPosition[min][1], sCharPosition[max][1] + 1) : "";
    }
	
	public static String minWindow3(String s, String t) {
		if(t.length() > s.length()) return "";
		int[] tCharCountArr = new int[128];
		char[] tCharArr = t.toCharArray();
		for(int i = 0; i < tCharArr.length; i++) {
			tCharCountArr[tCharArr[i]]++;
		}
		
		char[] sCharArr = s.toCharArray();
		int[][] sCharPosition = new int[sCharArr.length][2];// 记录位置
		int index = 0;
		for(int i = 0; i < sCharArr.length; i++) {
			if(tCharCountArr[sCharArr[i]] > 0) {
				sCharPosition[index][0] = sCharArr[i];
				sCharPosition[index++][1] = i;
			}
		}
		
		int count = 0;
		int[] currentWindowCharCount = new int[128];
		int l = 0, min = 0, max = 0, minLength = s.length();
		boolean flag = false;
		for(int r = 0; r < sCharPosition.length && sCharPosition[r][0] != 0; r++) {
			// 出现的字符都要记录，为的是冗余字符的判断
			currentWindowCharCount[sCharPosition[r][0]]++;
			// 某个字符满足条件之后就不在增加count了
			if(currentWindowCharCount[sCharPosition[r][0]] <= tCharCountArr[sCharPosition[r][0]]) {
				count++;
			}
			
			while(count == t.length()) {// 当前窗口中已存在t中的所有字符
				flag = true;
				// 记录最小窗口的起止位置
				if(sCharPosition[r][1] - sCharPosition[l][1] < minLength) {
					max = r;// 结束位置
					min = l;// 开始位置
					minLength = sCharPosition[r][1] - sCharPosition[l][1];
				}
				char removeChar = (char)sCharPosition[l][0];
				if(currentWindowCharCount[removeChar] <= tCharCountArr[removeChar]) {// 判断窗口中是否存在多余的字符，如果存在多余的字符，那么下一个位置任然满足条件，l指针可以继续移动，
					// 否则不能满足所有字符存在的条件
					count--;
				}
				currentWindowCharCount[removeChar]--;
				l++;
			}
		}
		
		return flag ? s.substring(sCharPosition[min][1], sCharPosition[max][1] + 1) : "";
    }
	
	public static void main(String[] args) {
		
//		int i = 0;
//		if(i++ == 0)System.out.println("aaa");
		
		//System.out.println(minWindow("ADOBECODEBANC", "ABC"));
		System.out.println(minWindow2("AAb", "AAb"));
	}

}
